package leetcode;

/**
 * Created by Ghost on 2015/1/20 0020.
 */
public class Dungeon_Game {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][] w = new int[m][n];

        w[m-1][n-1] = 1-dungeon[m-1][n-1]>0?1-dungeon[m-1][n-1]:1;
        for(int i=m-2;i>=0;i--){
             w[i][n-1] = w[i+1][n-1]-dungeon[i][n-1]>0?w[i+1][n-1]-dungeon[i][n-1]:1;
        }
        for(int i=n-2;i>=0;i--)
            w[m-1][i] = w[m-1][i+1]-dungeon[m-1][i]>0?w[m-1][i+1]-dungeon[m-1][i]:1;

        for(int i=m-2;i>=0;i--){
            for(int j=n-2;j>=0;j--){
                int fromRight = w[i][j+1]-dungeon[i][j]>0?w[i][j+1]-dungeon[i][j]:1;
                int fromDown = w[i+1][j]-dungeon[i][j]>0?w[i+1][j]-dungeon[i][j]:1;
                w[i][j]=Math.min(fromRight,fromDown);
            }
        }
        return w[0][0];
    }
    public static void main(String[] args){
        Dungeon_Game dungeon_game = new Dungeon_Game();
        int[][] matrix = {{-9}};
        System.out.println(dungeon_game.calculateMinimumHP(matrix));
    }
}
